package com.exercises;


class Exercise81 {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1};
        System.out.println(search(arr, 2));
    }


    public static boolean search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int cursor = (left + right) / 2;
            if (nums[cursor] == target || nums[left] == target || nums[right] == target) {
                return true;
            }
            if (nums[left] == nums[right]) {
                left += 1;
                right -= 1;
                continue;
            }

            if (nums[left] <= nums[cursor]) {
                if (nums[left] <= target && target < nums[cursor]) {
                    right = cursor - 1;
                } else {
                    left = cursor + 1;
                }
            } else {
                if (nums[cursor] < target && target <= nums[right - 1]) {
                    left = cursor + 1;
                } else {
                    right = cursor - 1;
                }
            }


        }

        return false;
    }


}

